/*
	解法：哈希法（在一个集合里判断一个元素有没有出现过）
          数组两两组合，分别求和
		  利用一个求和集合中的元素查找另一个集合中的元素是否出现过
	为什么：时间复杂度最小
	时间复杂度：O(n²)，空间复杂度：O(n²)
 */

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution
{
public:
	int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
	{
		unordered_map<int, int> sumCount;
		int result = 0;
		
		// 枚举 nums1 和 nums2 所有可能的两数组合，并统计和出现的次数
		for (int i = 0; i < (int)nums1.size(); i++)
		{
			for (int j = 0; j < (int)nums2.size(); j++)
			{
				int sum = nums1[i] + nums2[j];
				sumCount[sum]++;
			}
		}
		
		// 枚举 nums3 和 nums4 所有可能的两数组合，查找是否存在与其相反数的和
		for (int k = 0; k < (int)nums3.size(); k++)
		{
			for (int l = 0; l < (int)nums4.size(); l++)
			{
				int sum = nums3[k] + nums4[l];
				if (sumCount.count(-sum))
				{
					result += sumCount[-sum];
				}
			}
		}
		
		return result;
	}
};

int main()
{
	Solution solution;
	
	vector<int> nums1 = {1, 2};
	vector<int> nums2 = {-2, -1};
	vector<int> nums3 = {-1, 2};
	vector<int> nums4 = {0, 2};
	
	int count = solution.fourSumCount(nums1, nums2, nums3, nums4);
	cout << "Number of tuples: " << count << endl;
	
	return 0;
}


